package 力扣.二分;

import java.util.Arrays;
import java.util.Random;

public class 数组中第k个最大元素215 {
    public static void main(String[] args) {
//        int[] ints = {3,2,1,5,6,4};
//        int[] ints = {3,2,3,1,2,4,5,5,6};
        int[] ints = {3};
        int a = findKthLargest(ints, 1);
        System.out.println(a);
    }
    public static int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length-k];
    }

    class Solution {
            Random random = new Random();

            public int findKthLargest(int[] nums, int k) {
                return quickSelect(nums, 0, nums.length - 1, nums.length - k);
            }

            public int quickSelect(int[] a, int l, int r, int index) {
                int q = randomPartition(a, l, r);//得到轴值（确定一个数的位置）
                if (q == index) {//判断轴值是否是要找的那个数
                    return a[q];//若是则直接返回
                } else {//若不是则判断大小，进入下一层递归重新得到新的轴值
                    return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
                }
            }

            public int randomPartition(int[] a, int l, int r) {
                int i = random.nextInt(r - l + 1) + l;
                swap(a, i, r);
                return partition(a, l, r);
            }

            public int partition(int[] a, int l, int r) {
                int x = a[r], i = l - 1; // x暂存 a[r],即最右边的元素
                for (int j = l; j < r; ++j) {
                    if (a[j] <= x) {// 使用 新的a[i] 将小于（小于等于都可以）轴值的元素放在从 l 开始的最左边
                        swap(a, ++i, j);// 即小于 x 的 放在左边，依次右移
                    }
                }
                swap(a, i + 1, r);//将 轴值（基准元素）放在中间，使轴值左边的都小于轴值 ，右边的都大于轴值 。也就确定了轴值的位置
                return i + 1;//将轴值返回
            }

            public void swap(int[] a, int i, int j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }

    }
}
